#!/usr/bin/python
from node import Node

def make_tree(preorder, inorder):
    '''Makes a tree from the preorder and inorder lists.'''

    if not preorder or not inorder:
        return None
    
    else:
        root = Node(first(preorder))
        left_sublist, right_sublist = split_at(inorder, root.key)
        if not left_sublist and right_sublist:
            #this deals with a problem with splitting the list;
            #since values are pushed to the left first we need to switch
            #the order if it's messed up.
            left_sublist, right_sublist = right_sublist, left_sublist
            
        #now get the sublists in preorder form
        left_sublist_preorder = preorder[1:len(left_sublist) + 1]
        right_sublist_preorder = preorder[
            (len(left_sublist) + 1):last_index(preorder)
            ]
        
        if len(left_sublist) != 1:
            root.left = make_tree(left_sublist_preorder, left_sublist)
        else:
            root.left = Node(left_sublist[0])
            
        if len(right_sublist) != 1:    
            root.right = make_tree(right_sublist_preorder, right_sublist)
        else:
            root.right = Node(right_sublist[0])
        return root

def last(L):
    '''Returns the last element of list L.'''

    return L[last_index(L)] if L else None

def last_index(L):
    '''Returns the position of L's last element.'''

    return len(L) - 1 if L else 0

def split_at(L, value):
    '''Splits the list L at first occurence of value. Returns a pair where
    the first element is the first part of the list and the second element
    is the other part.'''
    
    index = L.index(value)
    first_half = L[:index]
    second_half = L[(index + 1):]
    return first_half, second_half

def first(L):
    '''Returns the first element of list L.'''

    return L[0] if L else None

test = make_tree([7, 8],[7, 8])
print test.left.right.key